1. Field of the Invention
The present invention relates generally to techniques for improving performance for linear algebra routines, with special significance to optimizing the matrix multiplication process. More specifically, a hybrid full-packed data structure allows a subroutine based on a rectangular standard row/column major format to be used for standard packed triangular matrices, thereby providing a three-to-five times improvement in speed and a reduction in storage by a factor of two.
2. Description of the Related Art
Scientific computing relies heavily on linear algebra. In fact, the whole field of engineering and scientific computing takes advantage of linear algebra for computations. Linear algebra routines are also used in games and graphics rendering.
Typically, these linear algebra routines reside in a math library of a computer system that utilizes one or more linear algebra routines as a part of its processing. Linear algebra is also heavily used in analytic methods that include applications such as supply chain management, as well as numeric data mining and economic methods and models.
The reason that linear algebra is so ubiquitous is that most engineering/scientific problems comprise non-linear scenarios which are combined by modeling as an aggregation of linearized sections, each respectively described by linear equations. Therefore, a linear network is formed that can be described in matrix format. It is noted here that the terms “array” and “matrix” are used interchangeably in the discussion of the present invention.
In general, a matrix representation A can be “simplified” by making a plurality of coordinate transformations so that the solution then becomes trivial to obtain in the final coordinates. Common coordinate transformations include transformation into the identity matrix or into the LU (lower/upper) factors format. A lower triangular matrix is L, and an upper triangular matrix is U. Matrix A becomes equal to the product of L by U (i.e., LU).
The process of coordinate transformation wherein two coordinate systems are combined into a single coordinate system involves matrix multiplication. Hence, the present invention focuses particularly on techniques that will particularly enhance matrix multiplication, but is not so limited. Typically, these linear algebra subroutines are stored in a math library of a computer tool that utilizes one or more linear algebra routines as a part of its processing.
A number of methods are have been used to improve performance of new or existing computer architectures for linear algebra routines.
However, because linear algebra permeates so many applications, a need continues to exist to optimize performance of matrix processing, including the need for efficiency in storing matrix data.